package com.sort;

import java.util.Arrays;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/26 20:06
 * @description 桶排序
 */
public class BucketSort {
    public static void bucketSort(int[] arr, int n) {
        if (n <= 1) {
            return;
        }

        // 创建桶数组，每个桶初始为空数组
        int max = Arrays.stream(arr).max().getAsInt(); // 找到最大元素
        int min = Arrays.stream(arr).min().getAsInt(); // 找到最小元素
        int bucketSize = (max - min) / n + 1; // 计算桶的大小

        // 创建桶数组
        int[][] buckets = new int[n][0];

        // 将数组元素分配到各个桶中
        for (int i = 0; i < n; i++) {
            int index = (arr[i] - min) / bucketSize;
            buckets[index] = insert(buckets[index], arr[i]);
        }

        // 对每个桶进行排序，这里使用Java的Arrays.sort方法
        for (int i = 0; i < n; i++) {
            Arrays.sort(buckets[i]);
        }

        // 合并桶数组回原数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < buckets[i].length; j++) {
                arr[index++] = buckets[i][j];
            }
        }
    }

    // 插入元素到桶中，并保持桶内元素有序
    private static int[] insert(int[] bucket, int element) {
        int[] result = new int[bucket.length + 1];
        int resultIndex = 0;

        // 插入新元素前，将小于新元素的元素复制到结果数组
        while (resultIndex < bucket.length && bucket[resultIndex] < element) {
            result[resultIndex] = bucket[resultIndex];
            resultIndex++;
        }

        // 插入新元素
        result[resultIndex] = element;
        resultIndex++;

        // 将剩余的元素复制到结果数组
        while (resultIndex < result.length) {
            result[resultIndex] = bucket[resultIndex - 1];
            resultIndex++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
        int n = arr.length;
        bucketSort(arr, n);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}
